/***
 * 单调队列 单调栈
 * 59.I. 滑动窗口的最大值
 * 59.II. 队列的最大值
 * 33. 二叉搜索树的后序遍历序列
 * **/

#include <deque>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
using namespace std;

template <class T>
void print(const T &t)
{
    typename T::const_iterator it = t.cbegin();
    for (; it != t.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

void printBool(bool b)
{
    if (b) {
        cout << "True" << endl;
    } else {
        cout << "False" << endl;
    }
}

class Solution
{
public:
    // 59.I. 手写堆，bug未解决：调用std::remove直接把=val的全删掉了
#if 0
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        // 感觉要搞一个堆维护窗口最大值
        vector<int> res;
        vector<int> window(nums.begin(), nums.begin() + k);
        buildHeap(window, window.size());
        res.push_back(window.front());
        print(window);
        for (int i = k; i < nums.size(); ++i) {
            // 移除窗口左端，复杂度有点高啊
            window.erase(std::remove(window.begin(), window.end(), nums[i - k]), window.end());
            window.push_back(nums[i]);
            cout << "调整前" << endl;
            print(window);
            heapify(window, 0, window.size()); // O(logN);
            cout << "调整后" << endl;
            print(window);
            res.push_back(window.front());
        }
        return res;
    }

private:
    void heapify(vector<int> &nums, int dad, int length)
    {
        int son = 2 * dad + 1;
        while (son < length) {
            if (son + 1 < length && nums[son] < nums[son + 1]) {
                ++son;
            }
            if (nums[son] < nums[dad]) {
                break;
            }
            swap(nums[son], nums[dad]);
            dad = son;
            son = 2 * dad + 1;
        }
    }
    void buildHeap(vector<int> &nums, int length)
    {
        for (int i = length / 2 - 1; i >= 0; --i) {
            heapify(nums, i, length);
        }
    }
#endif
    // priority_que + std::pair
#if 0
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        vector<int> res;
        priority_queue<pair<int, int>> pq;
        for (int i = 0; i < k; ++i) {
            pq.push(pair<int, int>(nums[i], i));
        }
        for (int i = k; i < nums.size(); ++i) {
            pq.push(pair<int, int>(nums[i], i));
            // 保证堆顶元素的下标是否还在窗口内
            while (pq.top().second <= i - k) {
                pq.pop();
            }
            res.push_back(pq.top().first);
        }
        return res;
    }
#endif
    // 单调队列
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        deque<int> dq; // 维护一个单调不增队列
        vector<int> res;
        for (int i = 0; i < k; ++i) {
            while (!dq.empty() && dq.back() < nums[i]) {
                dq.pop_back();
            }
            dq.push_back(nums[i]);
        }
        if (!dq.empty()) {
            res.push_back(dq.front());
        }
        for (int i = k; i < nums.size(); ++i) {
            if (dq.front() == nums[i - k]) {
                dq.pop_front();
            }
            while (!dq.empty() && dq.back() < nums[i]) {
                dq.pop_back();
            }
            dq.push_back(nums[i]);
            res.push_back(dq.front());
        }
        return res;
    }

    // 33. 递归解法
#if 0
    bool verifyPostorder(vector<int> &postorder)
    {
        // BST 中序 左->根->右 特性：左<根<右
        // 后序     左->右->根
        return recur(postorder, 0, postorder.size() - 1);
    }

private:
    bool recur(vector<int> &postorder, int left, int right)
    {
        if (left >= right) {
            return true;
        }
        int root = postorder[right];
        int i = left;
        while (i < right) {
            if (postorder[i] > root) {
                break;
            }
            ++i;
        }
        int j = i;
        while (j < right) {
            if (postorder[j] < root) {
                break;
            }
            ++j;
        }
        return j == right && recur(postorder, left, i - 1) && recur(postorder, i, right - 1);
    }
#endif
    // 33. 单调栈解法
    bool verifyPostorder(vector<int> &postorder)
    {
        // 后序的逆序 根->右->左
        // 保证了元素是递增的，若遇小于栈顶元素，则说明进入左子树
        // 进入的左子树是哪个节点的？就是弹栈的过程。
        stack<int> stk;
        int top = INT32_MAX;
        int n = postorder.size();
        for (int i = n - 1; i >= 0; --i) {
            if (postorder[i] > top) {
                return false;
            }
            while (!stk.empty() && postorder[i] < stk.top()) {
                top = stk.top();
                stk.pop();
            }
            stk.push(postorder[i]);
        }
        return true;
    }
};

// 59.II.
class MaxQueue
{
public:
    int max_value()
    {
        if (!_dq.empty()) {
            return _dq.front();
        }
        return -1;
    }

    void push_back(int value)
    {
        while (!_dq.empty() && _dq.back() < value) {
            _dq.pop_back();
        }
        _dq.push_back(value);
        _q.push(value);
    }

    int pop_front()
    {
        if (_q.empty()) {
            return -1;
        }
        if (_q.front() == _dq.front()) {
            _dq.pop_front();
        }
        int ret = _q.front();
        _q.pop();
        return ret;
    }

private:
    deque<int> _dq; // 单调队列
    queue<int> _q;  // 存储队列
};

Solution solve = Solution();

void test59I()
{
    // vector<int> nums = {-7, -8, 7, 5, 7, 1, 6, 0};
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    print(solve.maxSlidingWindow(nums, k));
}

void test33()
{
    vector<int> postorder = {1, 6, 3, 2, 5};
    printBool(solve.verifyPostorder(postorder));
}

int main()
{
    // test59I();
    test33();
    return 0;
}